package leetcode101.tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Synhard
 * @version 1.0
 * @class Code7
 * @description 637. 二叉树的层平均值
 * 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
 *
 *
 * 示例 1：
 *
 * 输入：
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 输出：[3, 14.5, 11]
 * 解释：
 * 第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
 *
 * 提示：
 *
 * 节点值的范围在32位有符号整数范围内。
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-06-23 8:54
 */
public class Code7 {


    public static void main(String[] args) {

    }

    public static List<Double> averageOfLevels(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode head = new TreeNode();
        double sum;
        List<Double> res = new ArrayList<>();
        List<TreeNode> list; // 用来存储某一层的所有结点
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) { // 层序遍历
            list = new ArrayList<>();
            sum = 0.0;
            while (!queue.isEmpty()) {
                head = queue.pollFirst();
                list.add(head);
                sum += head.val;
            }
            res.add(sum / list.size());
            for (TreeNode node : list) {
                if (node.left != null) {
                    queue.addLast(node.left);
                }
                if (node.right != null) {
                    queue.addLast(node.right);
                }
            }
        }
        return res;
    }

}
/*
层序遍历
 */